'''
@author: Kevin Zhao
@data:Dec 02,2012 


@todo:feel difficult to decide the index of C where to put multiplication result

'''
'''create new matrix filled with all zeros as its content'''

def create_new_matrix(m, n):
    # Create empty matrix filled with all zeros
    new_matrix = [[0 for row in range(n)] for col in range(m)]
    return new_matrix

def dnc_mm(A, B, level, C):
    level = level + 1
    row_count_A = len(A)
    col_count_A = len(A[0])
    row_count_B = len(B[0])
    col_count_B = len(B)
    if row_count_A == 1:
        return A[0][0] * B[0][0]
    
    A11 = [A[i][0:col_count_A / 2] for i in xrange(0, row_count_A / 2)]
    A12 = [A[i][col_count_A / 2:] for i in xrange(0, row_count_A / 2)]
    A21 = [A[i][0:col_count_A / 2] for i in xrange(row_count_A / 2, row_count_A)]
    A22 = [A[i][col_count_A / 2:] for i in xrange(row_count_A / 2, row_count_A)]
    
    B11 = [B[i][0:col_count_B / 2] for i in xrange(0, row_count_B / 2)]
    B12 = [B[i][col_count_B / 2:] for i in xrange(0, row_count_B / 2)]
    B21 = [B[i][0:col_count_B / 2] for i in xrange(row_count_B / 2, row_count_B)]
    B22 = [B[i][col_count_B / 2:] for i in xrange(row_count_B / 2, row_count_B)]
    
    base = len(C) / level
    #C11 = A11*B11+A12*B21
    C[len(C) / level][2 * level] = dnc_mm(A11 , B11, level, C) + dnc_mm(A12, B21, level, C)
    #C12 = A11*B12 + A12*B22
    C[2 * level][2 * level + 1] = dnc_mm(A11 , B12, level, C) + dnc_mm(A12 , B22, level, C)
    #C21 = A21*B11+A22*B21
    C[2 * level + 1][2 * level] = dnc_mm(A21 , B11, level, C) + dnc_mm(A22 , B21, level, C)
    #C22 = A21*B12+A22*B22
    C[2 * level + 1][2 * level + 1] = dnc_mm(A21 , B12, level, C) + dnc_mm(A22, B22, level, C)


'''
TEST
'''
a = [[2, 3, 4, 7], [5, 6, 1, 2], [3, 4, 7, 3], [2, 3, 1, 2]]         # 4x4 matrix
b = [[4, 7, 6, 1], [5, 3, 2, 4], [7, 8, 7, 6], [9, 2, 7, 3]]       # 4x4 matrix

matrix_C = create_new_matrix(4, 4)
level = 0
print dnc_mm(a, b, level, matrix_C)
